﻿#include "FloydWarshall.h"

#define ENDLESS 999

/* Prototypes */
static void runFloyds(void);
static void runWarshalls(void);
static void warshalls(matrixADT graph);
static void floyds(matrixADT graph);
static int minN(int n1, int n2);

void runGraph() {
	int choice;
	
	system("cls");
	printf("-- Graphs --\n\n");
	printf(" %d. Warshall's algorithm\n %d. Floyd's algorithm\n 3. Back\n", WARSHALLS, FLOYDS);
	printf("\n => ");
	choice = GetInteger();
	
	while (choice != 3) {
		switch (choice) {
			case WARSHALLS:
				runWarshalls();
				system("pause");
				return;
			case FLOYDS:
				runFloyds();
				system("pause");
				return;
			default:
				printf("Wrong choice.\n");
				choice = GetInteger();
				break;
		}
	}
}

/* Runs Warshall's Algorithm */
static void runWarshalls(void) {
	matrixADT graph;
	int i, j, count=0;
	
	system("cls");
	printf("-- Warshall's Algorithm --\n");
	printf("Recommended graphs: graphWX.txt (X = 4/5/10/20/100/500)\n");
	printf("\n => ");
	graph = loadGraph(Concat("./graphs/", GetLine()));
	if (graph != NULL) {
		warshalls(graph);
		printGraph(graph);
		// Paths within the transistive closure:
		for (i=0; i<graph->size; i++)
			for (j=0; j<=graph->size; j++)
				if (graph->nodes[i][j] == 0)
					count++;
		printf("%d paths within the transistive closure.\n\n", count);
	}
}

/* Runs Floyd's Algorithm */
static void runFloyds(void) {
	matrixADT graph;
	int i, j, count=0;
	
	system("cls");
	printf("-- Floyd's Algorithm --\n");
	printf("Recommended graphs: graphX.txt (X = 1-4/Floyd)\n");
	printf("\n => ");
	graph = loadGraph(Concat("./graphs/", GetLine()));
	if (graph != NULL) {
		floyds(graph);
		printGraph(graph);
		// Pair of nodes:
		for (i=1; i<graph->size; i++)
			for (j=1; j<=graph->size; j++)
				if (graph->nodes[i][j] != ENDLESS)
					count++;
		printf("%d pairs of nodes with paths in-between.\n\n", count);
	}
}

/* Warshall's Algorithm
 * ---
 * Description: Warshall algorithm finds the transitive closure of a
 * directed graph
 */
static void warshalls(matrixADT graph) {
	int k, i, j;
	
	for (k=0; k<graph->size; k++)
		for (i=0; i<graph->size; i++)
			for (j=0; j<graph->size; j++)
				graph->nodes[i][j] = graph->nodes[i][j] || (graph->nodes[i][k] && graph->nodes[k][j]);
}

/* Floyd's Algorithm
 * ---
 * Description: The Floyd-Warshall algorithm is a graph analysis
 * algorithm for finding shortest paths in a weigthed, directed graph
 */
static void floyds(matrixADT graph) {
	int k, i, j;

	for (k=0; k<graph->size; k++)
		for (i=0; i<graph->size; i++)
			for (j=0; j<graph->size; j++)
				graph->nodes[i][j] = minNode(graph->nodes[i][j], graph->nodes[i][k] + graph->nodes[k][j]);
}

static int minNode(int n1, int n2) {
	return (n1 < n2 ? n1 : n2);
}